// 力扣剑指 Offer 28. 对称的二叉树
// https://leetcode.cn/problems/dui-cheng-de-er-cha-shu-lcof/
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 二叉树的根节点
func TreeRoot(root *TreeNode) bool {
	if root == nil {
		return true
	}
	return isSymmetric(root.Left, root.Right)
}

// 对左子树和右子树分别递归判断是否对称
func isSymmetric(left *TreeNode, right *TreeNode) bool {
	if left == nil && right == nil {
		return true
	}
	if left == nil || right == nil {
		return false
	}
	if left.Val != right.Val {
		return false
	}
	if !isSymmetric(left.Left, right.Right) || !isSymmetric(left.Right, right.Left) {
		return false
	}
	return true
}

func main() {
	tree1 := &TreeNode{Val: 1,
		Left: &TreeNode{Val: 2,
			Left:  &TreeNode{Val: 3},
			Right: &TreeNode{Val: 4},
		},
		Right: &TreeNode{Val: 2,
			Left:  &TreeNode{Val: 4},
			Right: &TreeNode{Val: 3},
		},
	}
	fmt.Println(TreeRoot(tree1)) //true

	tree2 := &TreeNode{Val: 1,
		Left: &TreeNode{Val: 2,
			Right: &TreeNode{Val: 3},
		},
		Right: &TreeNode{Val: 2,
			Right: &TreeNode{Val: 3},
		},
	}
	fmt.Println(TreeRoot(tree2)) //false
}
